{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sentence Similarity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: areSentencesSimilar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #句子相似性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们可以将一个句子表示为一个单词数组，例如，句子 <code>\"I am happy with leetcode\"</code> 可以表示为 <code>arr = [\"I\",\"am\",happy\",\"with\",\"leetcode\"]</code></p>\n",
    "\n",
    "<p>给定两个句子 <code>sentence1</code> 和 <code>sentence2</code> 分别表示为一个字符串数组，并给定一个字符串对 <code>similarPairs</code> ，其中&nbsp;<code>similarPairs[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>&nbsp;表示两个单词&nbsp;<code>x<sub>i</sub></code>&nbsp;and&nbsp;<code>y<sub>i</sub></code>&nbsp;是相似的。</p>\n",
    "\n",
    "<p>如果 <code>sentence1</code> 和 <code>sentence2</code> 相似则返回 <code>true</code> ，如果不相似则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>两个句子是相似的，如果:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>它们具有 <strong>相同的长度</strong> (即相同的字数)</li>\n",
    "\t<li><code>sentence1[i]</code>&nbsp;和&nbsp;<code>sentence2[i]</code>&nbsp;是相似的</li>\n",
    "</ul>\n",
    "\n",
    "<p>请注意，一个词总是与它自己相似，也请注意，相似关系是不可传递的。例如，如果单词 <code>a</code> 和 <code>b</code> 是相似的，单词&nbsp;<code>b</code> 和 <code>c</code> 也是相似的，那么 <code>a</code> 和 <code>c</code>&nbsp; <strong>不一定相似</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> sentence1 = [\"great\",\"acting\",\"skills\"], sentence2 = [\"fine\",\"drama\",\"talent\"], similarPairs = [[\"great\",\"fine\"],[\"drama\",\"acting\"],[\"skills\",\"talent\"]]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 这两个句子长度相同，每个单词都相似。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> sentence1 = [\"great\"], sentence2 = [\"great\"], similarPairs = []\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 一个单词和它本身相似。</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> sentence1 = [\"great\"], sentence2 = [\"doubleplus\",\"good\"], similarPairs = [[\"great\",\"doubleplus\"]]\n",
    "<strong>输出:</strong> false\n",
    "<strong>解释: </strong>因为它们长度不同，所以返回false。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= sentence1.length, sentence2.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= sentence1[i].length, sentence2[i].length &lt;= 20</code></li>\n",
    "\t<li><code>sentence1[i]</code>&nbsp;和&nbsp;<code>sentence2[i]</code>&nbsp;只包含大小写英文字母</li>\n",
    "\t<li><code>0 &lt;= similarPairs.length &lt;= 2000</code></li>\n",
    "\t<li><code>similarPairs[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= x<sub>i</sub>.length, y<sub>i</sub>.length &lt;= 20</code></li>\n",
    "\t<li>所有对&nbsp;<code>(xi, yi)</code>&nbsp;都是 <strong>不同</strong> 的</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sentence-similarity](https://leetcode.cn/problems/sentence-similarity/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sentence-similarity](https://leetcode.cn/problems/sentence-similarity/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"great\",\"acting\",\"skills\"]\\n[\"fine\",\"drama\",\"talent\"]\\n[[\"great\",\"fine\"],[\"drama\",\"acting\"],[\"skills\",\"talent\"]]', '[\"great\"]\\n[\"great\"]\\n[]', '[\"great\"]\\n[\"doubleplus\",\"good\"]\\n[[\"great\",\"doubleplus\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        #一眼并查集\n",
    "        if len(sentence1)!=len(sentence2):\n",
    "            return False\n",
    "        parent={}\n",
    "        for a,b in similarPairs:\n",
    "            parent[a]=a\n",
    "            parent[b]=b\n",
    "        for i in range(len(sentence1)):\n",
    "            parent[sentence1[i]]=sentence1[i]\n",
    "            parent[sentence2[i]]=sentence2[i]\n",
    "        def find(i):\n",
    "            if parent[i]==i:\n",
    "                return i\n",
    "            else:\n",
    "                parent[i]=find(parent[i])\n",
    "                return parent[i]\n",
    "        def union(i,j):\n",
    "            x,y=find(i),find(j)\n",
    "            parent[x]=y\n",
    "        for i,j in similarPairs:\n",
    "            union(i,j)\n",
    "        for i in range(len(sentence2)):\n",
    "            x,y=sentence1[i],sentence2[i]\n",
    "            if find(x)!=find(y):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, x) -> None:\n",
    "        self.uf = [-1] * x\n",
    "\n",
    "    def find(self, x):\n",
    "        r = x\n",
    "        while self.uf[x] >= 0:\n",
    "            x = self.uf[x]\n",
    "\n",
    "        while r != x:\n",
    "            self.uf[r], r = x, self.uf[r]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        ux, uy = self.find(x), self.find(y)\n",
    "        if ux == uy:\n",
    "            return\n",
    "        if self.uf[ux] >= self.uf[uy]:\n",
    "            self.uf[uy] += self.uf[ux]\n",
    "            self.uf[ux] = uy\n",
    "        else:\n",
    "            self.uf[ux] += self.uf[uy]\n",
    "            self.uf[uy] = ux\n",
    "        return\n",
    "\n",
    "    def count(self):\n",
    "        ans = 0\n",
    "        for c in self.uf:\n",
    "            if c < 0 and c != -1:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "    def valid(self):\n",
    "        n = len(self.uf)\n",
    "        for c in range(n):\n",
    "            if self.uf[c] == -n:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def __print__(self):\n",
    "        return self.uf\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        m = {}\n",
    "        v = set()\n",
    "        for s in sentence1 + sentence2:\n",
    "            v.add(s)\n",
    "        for s1,s2 in similarPairs:\n",
    "            v.add(s1)\n",
    "            v.add(s2)\n",
    "        v = list(v)\n",
    "        cur = 0\n",
    "        rm = {}\n",
    "        uf = UnionFind(len(v))\n",
    "        for i in range(len(v)):\n",
    "            m[i] = v[i]\n",
    "            rm[v[i]] = i\n",
    "        for s1,s2 in similarPairs:\n",
    "            uf.union(rm[s1],rm[s2])\n",
    "        for i in range(len(sentence1)):\n",
    "            s1,s2 = sentence1[i],sentence2[i]\n",
    "            if s1 not in rm or s2 not in rm:\n",
    "                if s1 != s2:\n",
    "                    return False\n",
    "            r1,r2 = uf.find(rm[s1]),uf.find(rm[s2])\n",
    "            if r1 != r2:\n",
    "                return False\n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        fa=dict()\n",
    "        def find(x):\n",
    "            #print(x)\n",
    "            if x not in fa:\n",
    "                fa[x]=x\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(a,b):\n",
    "            if find(a)!=find(b):\n",
    "                fa[find(a)]=find(b)\n",
    "        for a,b in similarPairs:\n",
    "            union(a,b)\n",
    "        n=len(sentence1)\n",
    "        if len(sentence2)!=n:\n",
    "            return False \n",
    "        for i in range(n):\n",
    "            if find(sentence1[i])!=find(sentence2[i]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        _set = set()  \n",
    "        for x in sentence1 + sentence2:\n",
    "            _set.add(x)\n",
    "        for x,y in similarPairs:\n",
    "            _set.add(x)\n",
    "            _set.add(y)\n",
    "        \n",
    "        arr = list(_set) \n",
    "        n = len(arr)\n",
    "        fa = list(range(n))\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def union(x,y):\n",
    "            fa[find(x)] = find(y)\n",
    "        \n",
    "        def same(x,y):\n",
    "            return find(x) == find(y)\n",
    "\n",
    "        d = {x:i for i,x in enumerate(arr)}\n",
    "        \n",
    "        for x,y in similarPairs:\n",
    "            union(d[x], d[y])\n",
    "\n",
    "        for x,y in zip(sentence1,sentence2):\n",
    "            if x != y and not same(d[x],d[y]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "'''\n",
    "--- 从此处复制 ---\n",
    "'''\n",
    "class IdentityDefaultDict(defaultdict):\n",
    "    '''\n",
    "    该类用于处理并查集初始化的恒等映射\n",
    "    '''\n",
    "    def __missing__(self, key):\n",
    "        return key\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n=None):\n",
    "        self.parent = IdentityDefaultDict()\n",
    "        if n: self.parent = list(range(n))\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y: self.parent[x] = y\n",
    "    def count_groups(self):\n",
    "        return len(set(self.find(x) for x in self.parent))\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        uf = UnionFind()\n",
    "        for x, y in similarPairs:\n",
    "            uf.merge(x, y)\n",
    "        if len(sentence1) != len(sentence2): return False\n",
    "        for x, y in zip(sentence1, sentence2):\n",
    "            if uf.find(x) != uf.find(y): return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        #一眼并查集\n",
    "        if len(sentence1)!=len(sentence2):\n",
    "            return False\n",
    "        parent={}\n",
    "        for a,b in similarPairs:\n",
    "            parent[a]=a\n",
    "            parent[b]=b\n",
    "        for i in range(len(sentence1)):\n",
    "            parent[sentence1[i]]=sentence1[i]\n",
    "            parent[sentence2[i]]=sentence2[i]\n",
    "        def find(i):\n",
    "            if parent[i]==i:\n",
    "                return i\n",
    "            else:\n",
    "                parent[i]=find(parent[i])\n",
    "                return parent[i]\n",
    "        def union(i,j):\n",
    "            x,y=find(i),find(j)\n",
    "            parent[x]=y\n",
    "        for i,j in similarPairs:\n",
    "            union(i,j)\n",
    "        for i in range(len(sentence2)):\n",
    "            x,y=sentence1[i],sentence2[i]\n",
    "            if find(x)!=find(y):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "    def add(self, x: str):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "        \n",
    "    def merge(self, x: str, y: str):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "    def find(self, x: str):\n",
    "        root = x\n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "        while root != x:\n",
    "            original_father = self.father[x]\n",
    "            self.father[x] = root\n",
    "            x = original_father\n",
    "        return root\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        uf = UnionFind()\n",
    "        for word1, word2 in similarPairs:\n",
    "            uf.add(word1)\n",
    "            uf.add(word2)\n",
    "            uf.merge(word1, word2)\n",
    "        for i in range(len(sentence1)):\n",
    "            w1, w2 = sentence1[i], sentence2[i]\n",
    "            if w1 == w2 or (w1 in uf.father and w2 in uf.father and uf.find(sentence1[i]) == uf.find(sentence2[i])):\n",
    "                continue\n",
    "            return False\n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    sentences are similar:\n",
    "    1. same length\n",
    "    2. the word in the same position had the same final root\n",
    "    '''\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2) or not similarPairs:\n",
    "            return False \n",
    "\n",
    "        n = len(similarPairs)\n",
    "        id = defaultdict(str)\n",
    "\n",
    "        for pair in similarPairs: # find all words relationship\n",
    "            if pair[0] not in id:\n",
    "                id[pair[0]] = pair[0]\n",
    "            if pair[1] not in id:\n",
    "                id[pair[1]] = pair[1]\n",
    "            p = self.find_root(id, pair[0])  \n",
    "            q = self.find_root(id, pair[1])\n",
    "            id[q] = p \n",
    "\n",
    "        for i in id:\n",
    "            id[i] = self.find_root(id, i)\n",
    "        \n",
    "        for i in range(len(sentence1)): # go over every position\n",
    "            if id[sentence1[i]] == id[sentence2[i]] or id[sentence2[i]] == id[sentence1[i]]:\n",
    "                continue\n",
    "            else:\n",
    "                return False \n",
    "        return True\n",
    "\n",
    "    def find_root(self, id, i):\n",
    "        while i != id[i]:\n",
    "            id[i] = id[id[i]]\n",
    "            i = id[i]\n",
    "        return i "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        \n",
    "        p=collections.defaultdict()\n",
    "        \n",
    "        if len(sentence1)!=len(sentence2):\n",
    "            return False\n",
    "        \n",
    "        n=len(sentence1)\n",
    "        for a,b in zip(sentence1,sentence2):\n",
    "            p[a]=a\n",
    "            p[b]=b\n",
    "        \n",
    "        def find(x):\n",
    "            if p[x]==x:\n",
    "                return p[x]\n",
    "            p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def union(x,y):\n",
    "            p[find(x)]=find(y)\n",
    "        \n",
    "        for x,y in similarPairs:\n",
    "            if x not in p:\n",
    "                p[x]=x \n",
    "            if y not in p :\n",
    "                p[y]=y\n",
    "            union(x,y)\n",
    "        \n",
    "        for a,b in zip(sentence1,sentence2):\n",
    "            if find(a)!=find(b):\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.part = n\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for x in range(n)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_part_size(self, x):\n",
    "        root_x = self.find(x)\n",
    "        return self.size[root_x]\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2): return False\n",
    "\n",
    "        words = set(sentence1).union(set(sentence2))\n",
    "        for word1, word2 in similarPairs:\n",
    "            words.add(word1)\n",
    "            words.add(word2)\n",
    "        words = list(words)\n",
    "        words_dict = {word: i for i, word in enumerate(words)}\n",
    "\n",
    "        uf = UnionFind(len(words))\n",
    "        for word1, word2 in similarPairs:\n",
    "            uf.union(words_dict[word1], words_dict[word2])\n",
    "        \n",
    "        for i in range(len(sentence1)):\n",
    "            if not uf.is_connected(words_dict[sentence1[i]], words_dict[sentence2[i]]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        m, n = len(sentence1), len(sentence2)\n",
    "        if m != n: return False\n",
    "        q = len(similarPairs)\n",
    "        g = defaultdict(list)\n",
    "        for x, y in similarPairs:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        for x, y in zip(sentence1, sentence2):\n",
    "            if x == y: continue\n",
    "            st = [x]\n",
    "            vis = set()\n",
    "            vis.add(x)\n",
    "            while st:\n",
    "                cur = st.pop()\n",
    "                if cur == y: break\n",
    "                for z in g[cur]:\n",
    "                    if z not in vis:\n",
    "                        vis.add(z)\n",
    "                        st.append(z)\n",
    "            else:\n",
    "                return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        p = defaultdict(str) \n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False \n",
    "        def find(x):\n",
    "            if x not in p:\n",
    "                p[x] = x \n",
    "                return x \n",
    "            if x == p[x]:\n",
    "                return x \n",
    "            p[x] = find(p[x]) \n",
    "            return p[x] \n",
    "        def un(x, y):\n",
    "            fx,fy = find(x), find(y)\n",
    "            if fx == fy:\n",
    "                return False \n",
    "            else:\n",
    "                p[fy] = fx \n",
    "                return True \n",
    "        def same(x,y):\n",
    "            fx,fy = find(x), find(y)\n",
    "            return fx == fy\n",
    "\n",
    "        for a, b in similarPairs:\n",
    "            un(a,b)\n",
    "\n",
    "        for a, b in zip(sentence1, sentence2):\n",
    "            if not same(a,b):\n",
    "                return False \n",
    "        return True \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        parents = {}\n",
    "        for x, y in similarPairs:\n",
    "            parents[x] = x\n",
    "            parents[y] = y\n",
    "        def find(index):\n",
    "            if parents[index] != index:\n",
    "                return find(parents[index])\n",
    "            return parents[index]\n",
    "        def union(index1, index2):\n",
    "            parents[find(index1)] = find(index2)\n",
    "        for x, y in similarPairs:\n",
    "            union(x, y)\n",
    "        for x, y in zip(sentence1, sentence2):\n",
    "            if (x == y) or (x in parents and y in parents and find(x) == find(y)):\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 思路的心得：\n",
    "# 本质 无向图 两点间的连通性\n",
    "# 能给每个对象（结点）赋唯一ID号。则无脑并查集\n",
    "\n",
    "class UnionFind:        #### 手写并查集\n",
    "    def __init__(self, n):\n",
    "        self.parent = [x for x in range(n)]     #直系师傅，父指针\n",
    "        self.size = [1 for _ in range(n)]       #某个人手下的人数\n",
    "        self.part = n                           #江湖上门派的个数==图中连通域的个数\n",
    "    \n",
    "    def Find(self, x: int) -> int:  #寻找掌门\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        return self.Find(self.parent[x])\n",
    "    \n",
    "    def Union(self, x: int, y: int) -> bool:    #两个人合并为一个门派\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:    #判断两人是否在同一门派\n",
    "        return self.Find(x) == self.Find(y)\n",
    "    \n",
    "    def get_part_size(self, x: int) -> int:         #所在门派的人数\n",
    "        root_x = self.Find(x)\n",
    "        return self.size[root_x]\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:\n",
    "        if len(words1) != len(words2):      #长度不同，必不相似\n",
    "            return False\n",
    "        n = len(words1)\n",
    "        UF = UnionFind(2 * len(pairs))      #并查集\n",
    "        word_ID = defaultdict(int)          #单词和它的唯一ID号\n",
    "        ID = 0\n",
    "        for pair in pairs:\n",
    "            for w in pair:\n",
    "                if w not in word_ID:\n",
    "                    word_ID[w] = ID\n",
    "                    ID += 1\n",
    "            UF.Union(word_ID[pair[0]], word_ID[pair[1]])    #每一对都是连通的（无向图中）\n",
    "        \n",
    "        for w1, w2 in zip(words1, words2):\n",
    "            if w1 == w2:        #同一个单词，必然相似\n",
    "                continue\n",
    "            else:\n",
    "                if w1 in word_ID and w2 in word_ID: #在pairs中出现过\n",
    "                    if UF.connected(word_ID[w1], word_ID[w2]) == True:  #相似==无向图中连通==两人在同一个门派\n",
    "                        continue\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(\n",
    "        self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]\n",
    "    ) -> bool:\n",
    "        m, n = len(sentence1), len(sentence2)\n",
    "        if m != n:\n",
    "            return False\n",
    "        root = {}\n",
    "\n",
    "        def find(i):\n",
    "            if i not in root:\n",
    "                root[i] = i\n",
    "            elif root[i] != i:\n",
    "                root[i] = find(root[i])\n",
    "            return root[i]\n",
    "\n",
    "        def union(i, j):\n",
    "            ri, rj = find(i), find(j)\n",
    "            if ri != rj:\n",
    "                root[rj] = ri\n",
    "\n",
    "        for i, j in similarPairs:\n",
    "            union(i, j)\n",
    "        for i in range(n):\n",
    "            if find(sentence2[i]) != find(sentence1[i]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1]*n\n",
    "        self.part = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.root[x]:\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            root_x = self.find(self.root[x])\n",
    "            self.root[x] = root_x\n",
    "            return root_x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        m, n = len(sentence1), len(sentence2)\n",
    "        if m != n: return False\n",
    "        \n",
    "        words = set(sentence1).union(set(sentence2))\n",
    "        for word1, word2 in similarPairs:\n",
    "            words.add(word1)\n",
    "            words.add(word2)\n",
    "        \n",
    "        words = list(words)\n",
    "        dic = {word: i for i, word in enumerate(words)}\n",
    "        uf = UnionFind(len(words))\n",
    "\n",
    "        for word1, word2 in similarPairs:\n",
    "            uf.union(dic[word1], dic[word2])\n",
    "        \n",
    "        for i in range(m):\n",
    "            if not uf.is_connected(dic[sentence1[i]], dic[sentence2[i]]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.part = n\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for x in range(n)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_part_size(self, x):\n",
    "        root_x = self.find(x)\n",
    "        return self.size[root_x]\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2): return False\n",
    "\n",
    "        words = set(sentence1).union(set(sentence2))\n",
    "        for word1, word2 in similarPairs:\n",
    "            words.add(word1)\n",
    "            words.add(word2)\n",
    "        words = list(words)\n",
    "        words_dict = {word: i for i, word in enumerate(words)}\n",
    "\n",
    "        uf = UnionFind(len(words))\n",
    "        for word1, word2 in similarPairs:\n",
    "            uf.union(words_dict[word1], words_dict[word2])\n",
    "        \n",
    "        for i in range(len(sentence1)):\n",
    "            if not uf.is_connected(words_dict[sentence1[i]], words_dict[sentence2[i]]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        def bfs(src, id) -> None:\n",
    "            q = deque([src])\n",
    "            seen.add(src)\n",
    "            while q:\n",
    "                cur = q.popleft()\n",
    "                word_id[cur] = id\n",
    "                for nxt in graph[cur]:\n",
    "                    if nxt not in seen:\n",
    "                        q.append(nxt)\n",
    "                        seen.add(nxt)\n",
    "        \n",
    "        if len(sentence1) != len(sentence2):  # edge case\n",
    "            return False\n",
    "        graph = defaultdict(set)\n",
    "        for u, v in similarPairs:  # build graph\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        # BFS\n",
    "        seen = set()\n",
    "        word_id = {}  # word -> id\n",
    "        id = 0\n",
    "        for word in graph.keys():  # mark components\n",
    "            if word not in seen:\n",
    "                bfs(word, id)\n",
    "                id += 1\n",
    "        return all(w1 == w2 or (w1 in word_id and w2 in word_id and word_id[w1] == word_id[w2]) for w1, w2 in\n",
    "                   zip(sentence1, sentence2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        if sentence1 == sentence2:\n",
    "            return True\n",
    "        sentence1 = sentence1.split(' ')\n",
    "        sentence2 = sentence2.split(' ')\n",
    "        if len(sentence1) >= len(sentence2):\n",
    "            s = sentence1\n",
    "            ss = sentence2\n",
    "        else:\n",
    "            s = sentence2\n",
    "            ss = sentence1\n",
    "        for i in range(len(s) + 1):\n",
    "            for j in range(i+1,len(s)+1):\n",
    "                if s[:i] + s[j:] == ss:\n",
    "                    return True\n",
    "        return False\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        if len(sentence2) > len(sentence1):\n",
    "            sentence1, sentence2 = sentence2, sentence1\n",
    "        s1, s2, left, right = sentence1.split(), sentence2.split(), 0, -1\n",
    "        while left - right <= len(s2):\n",
    "            if s1[left] == s2[left]:\n",
    "                left += 1\n",
    "            elif s1[right] == s2[right]:\n",
    "                right -= 1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "\n",
    "        sentence1 = sentence1.split(\" \")\n",
    "        sentence2 = sentence2.split(\" \")\n",
    "\n",
    "        m = len(sentence1)\n",
    "        n = len(sentence2)\n",
    "\n",
    "        if m < n:\n",
    "            m, n = n, m\n",
    "            sentence1, sentence2 = sentence2, sentence1\n",
    "        \n",
    "        i = 0\n",
    "        j = 0\n",
    "\n",
    "        while i < n and sentence1[i] == sentence2[i]:\n",
    "            i = i + 1\n",
    "        \n",
    "        while j < n and sentence1[m-1-j] == sentence2[n-1-j]:\n",
    "            j = j + 1\n",
    "        \n",
    "        return i + j >= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "\n",
    "        s1 =  sentence1.split()\n",
    "        s2 =  sentence2.split()\n",
    "        i,j = 0,0\n",
    "        while i < len(s1) and i <len(s2) and s1[i] == s2[i]:\n",
    "            i+=1\n",
    "        while j < len(s1) - i and j <len(s2) -i  and s1[-j-1] == s2[-j-1]:\n",
    "            j+=1\n",
    "        return i + j == min(len(s1), len(s2))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        # 双端队列\n",
    "        # q1 = deque(sentence1.split())\n",
    "        # q2 = deque(sentence2.split())\n",
    "        # while q1 and q2 and q1[0] == q2[0]:\n",
    "        #     q1.popleft()\n",
    "        #     q2.popleft()\n",
    "        # while q1 and q2 and q1[-1] == q2[-1]:\n",
    "        #     q1.pop()\n",
    "        #     q2.pop()\n",
    "        # return not q1 or not q2 \n",
    "\n",
    "        # 双指针\n",
    "        w1, w2 = sentence1.split(), sentence2.split()\n",
    "        m, n = len(w1), len(w2)\n",
    "        if m < n:\n",
    "            w1, w2 = w2, w1\n",
    "            m, n = n, m\n",
    "        i = j = 0\n",
    "        while i < n and w1[i] == w2[i]:\n",
    "            i += 1\n",
    "        while j < n and w1[m-1-j] == w2[n-1-j]:\n",
    "            j += 1\n",
    "        return i + j >= n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        words1, words2 = sentence1.split(), sentence2.split()\n",
    "        m, n = len(words1), len(words2)\n",
    "        if m < n:\n",
    "            words1, words2 = words2, words1\n",
    "            m, n = n, m\n",
    "        i = j = 0\n",
    "        while i < n and words1[i] == words2[i]:\n",
    "            i += 1\n",
    "        while j < n and words1[m - 1 - j] == words2[n - 1 - j]:\n",
    "            j += 1\n",
    "        return i + j >= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        words1 = sentence1.split()\n",
    "        words2 = sentence2.split()\n",
    "\n",
    "        words1, words2 = (words1, words2) if len(words1) <= len(words2) else (words2, words1)\n",
    "\n",
    "        i, j = 0, 0\n",
    "        found_diff = False\n",
    "\n",
    "        while i < len(words1) and j < len(words2):\n",
    "            if words1[i] == words2[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                found_diff = True\n",
    "                break\n",
    "\n",
    "        if not found_diff:\n",
    "            return True\n",
    "        else:\n",
    "            ii, jj = len(words1) - 1, len(words2) - 1\n",
    "\n",
    "            while ii >= i and jj >= j:\n",
    "                if words1[ii] != words2[jj]:\n",
    "                    return False\n",
    "                else:\n",
    "                    ii -= 1\n",
    "                    jj -= 1\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        # 数组化, 并将sentence1设置为较短的字符串\n",
    "        s1 = sentence1.split(' ')\n",
    "        s2 = sentence2.split(' ')\n",
    "        n1, n2 = len(s1), len(s2)\n",
    "        if n1 > n2:\n",
    "            s1, s2 = s2, s1\n",
    "            n1, n2 = n2, n1\n",
    "\n",
    "        # 先判断s1出现在s2首尾的情况\n",
    "        if s1 == s2[:n1] or s1 == s2[-n1:]:\n",
    "            return True\n",
    "\n",
    "        # 现在只剩下一种情况, 即在s1的某两个单词中间 添加后, 成为s2\n",
    "        p1 = p2 = 0\n",
    "        while s1[p1] == s2[p2]:\n",
    "            p1 += 1\n",
    "            p2 += 1\n",
    "\n",
    "        p2 = n2-1\n",
    "        for i in range(n1-1, p1-1, -1):\n",
    "            if s1[i] != s2[p2]:\n",
    "                return False\n",
    "            p2 -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        stc1=sentence1.strip().split()\n",
    "        stc2=sentence2.strip().split()\n",
    "        i,j=0,0\n",
    "        while i < len(stc1) and i < len(stc2) and stc1[i]==stc2[i]:\n",
    "            i+=1\n",
    "        while j < len(stc1)-i and j < len(stc2)-i and stc1[-j-1]==stc2[-j-1]:\n",
    "            j+=1\n",
    "        print(i,j)\n",
    "        return i+j==min(len(stc1),len(stc2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        words1 = sentence1.split()\n",
    "        words2 = sentence2.split()\n",
    "\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < len(words1) and i < len(words2) and words1[i] == words2[i]:\n",
    "            i += 1\n",
    "        while j < len(words1) - i and j < len(words2) - i and words1[-j - 1] == words2[-j-1]:\n",
    "            j += 1\n",
    "\n",
    "        return i + j == min(len(words1), len(words2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        ll1 = sentence1.strip().split()\n",
    "        ll2 = sentence2.strip().split()\n",
    "        \n",
    "        if not ll1 or not ll2:\n",
    "            return True\n",
    "        \n",
    "        ilen1 = len(ll1)\n",
    "        ilen2 = len(ll2)\n",
    "        ilen = min(ilen1,ilen2)\n",
    "        i, j = 0, 0\n",
    "        while i < ilen and ll1[i] == ll2[i]:\n",
    "            i += 1\n",
    "        while j < ilen and ll1[-1-j] == ll2[-1-j]:\n",
    "            j += 1\n",
    "        \n",
    "        return True if i+j >= ilen else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        s1 = sentence1.split()\n",
    "        s2 = sentence2.split()\n",
    "        if len(s1) > len(s2):\n",
    "            s1, s2 = s2, s1\n",
    "        for i in range(len(s1) + 1):\n",
    "            start, end = s1[:i], s1[i:len(s1)]\n",
    "            # print(s1, i, start, end)\n",
    "            if start == s2[:i] and end == s2[i + len(s2) - len(s1):len(s2)]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        # 双端队列\n",
    "        q1 = deque(sentence1.split())\n",
    "        q2 = deque(sentence2.split())\n",
    "        while q1 and q2 and q1[0] == q2[0]:\n",
    "            q1.popleft()\n",
    "            q2.popleft()\n",
    "        while q1 and q2 and q1[-1] == q2[-1]:\n",
    "            q1.pop()\n",
    "            q2.pop()\n",
    "        return not q1 or not q2 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        if sentence1 == sentence2:\n",
    "            return True\n",
    "        sentence1 = sentence1.split(' ')\n",
    "        sentence2 = sentence2.split(' ')\n",
    "        if len(sentence1) >= len(sentence2):\n",
    "            s = sentence1\n",
    "            ss = sentence2\n",
    "        else:\n",
    "            s = sentence2\n",
    "            ss = sentence1\n",
    "        i = 0\n",
    "        while ss:\n",
    "            if s[0] == ss[0]:\n",
    "                ss.pop(0)\n",
    "                s.pop(0)\n",
    "            elif s[-1] == ss[-1]:\n",
    "                ss.pop()\n",
    "                s.pop()\n",
    "            else:\n",
    "                break\n",
    "        if not ss:\n",
    "            return True\n",
    "        return False\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        sentence1 = sentence1.split(' ')\n",
    "        sentence2 = sentence2.split(' ')\n",
    "        if len(sentence1) == len(sentence2):\n",
    "            return sentence1 == sentence2\n",
    "        if len(sentence1) < len(sentence2):\n",
    "            sentence1, sentence2 = sentence2, sentence1\n",
    "        for i in range(len(sentence2)):\n",
    "            if sentence2[i] != sentence1[i]:\n",
    "                return sentence2[i:] == sentence1[(len(sentence1) - len(sentence2) + i):]\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        lst1 = sentence1.split(\" \")\n",
    "        lst2 = sentence2.split(\" \")\n",
    "        if len(lst1) == len(lst2):\n",
    "            return lst1 == lst2\n",
    "        if len(lst1) < len(lst2):\n",
    "            lst2, lst1 = lst1, lst2\n",
    "        m = len(lst2)\n",
    "        n = len(lst1)\n",
    "        for i in range(m):\n",
    "            if lst1[:i] == lst2[:i] and lst1[-(m-i):] == lst2[-(m-i):]:\n",
    "                return True\n",
    "        if lst2 == lst1[:m]:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "\n",
    "        s1 =  sentence1.split()\n",
    "        s2 =  sentence2.split()\n",
    "        i,j = 0,0\n",
    "        while i < len(s1) and i <len(s2) and s1[i] == s2[i]:\n",
    "            i+=1\n",
    "        while j < len(s1) - i and j <len(s2) -i  and s1[-j-1] == s2[-j-1]:\n",
    "            j+=1\n",
    "        return i + j == min(len(s1), len(s2))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        l1 = sentence1.split()\n",
    "        l2 = sentence2.split()\n",
    "        # 确保l1更长\n",
    "        if len(l1) < len(l2):\n",
    "            l1, l2 = l2, l1\n",
    "        \n",
    "        cur = 0\n",
    "        for w in l1:\n",
    "            if l2[cur] != w:\n",
    "                l2 = l2[cur:]\n",
    "                break\n",
    "            cur += 1\n",
    "            if cur == len(l2):\n",
    "                return True\n",
    "        l1.reverse()\n",
    "        l2.reverse()\n",
    "        cur = 0\n",
    "        for w in l1:\n",
    "            if l2[cur] != w:\n",
    "                return False\n",
    "            cur += 1\n",
    "            if cur == len(l2):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        sentence1=sentence1.split()\n",
    "        sentence2=sentence2.split()\n",
    "        n1,n2=len(sentence1),len(sentence2)\n",
    "        i=j=0\n",
    "        while i<n1 and i<n2 and sentence1[i]==sentence2[i]:\n",
    "            i+=1\n",
    "        while j<n1-i and j<n2-i and sentence1[-j-1]==sentence2[-j-1]:\n",
    "            j+=1\n",
    "        return i+j==min(n1,n2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "      sentence1 = sentence1.split(' ')\n",
    "      sentence2 = sentence2.split(' ')\n",
    "      n = len(sentence1)\n",
    "      m = len(sentence2)\n",
    "      if sentence1 == sentence2:\n",
    "        return True\n",
    "      if n < m:\n",
    "        sentence1, sentence2 = sentence2, sentence1\n",
    "        n, m = m, n\n",
    "      left, right = 0, len(sentence2)-1\n",
    "      while left <= right and sentence1[left] == sentence2[left]:\n",
    "        left += 1\n",
    "      while left <= right and sentence2[right] == sentence1[n-(m-right)]:\n",
    "        right -= 1\n",
    "      return left > right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        sen1_list=sentence1.split(' ')\n",
    "        sen2_list=sentence2.split(' ')\n",
    "        i=0\n",
    "        j=0\n",
    "        while i<len(sen1_list) and i<len(sen2_list) and sen1_list[i]==sen2_list[i]:\n",
    "            i+=1\n",
    "        while j<len(sen1_list)-i and j<len(sen2_list)-i and sen1_list[-j-1]==sen2_list[-j-1]:\n",
    "            j+=1\n",
    "        return i+j==min(len(sen1_list),len(sen2_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        words1 = sentence1.split()\n",
    "        words2 = sentence2.split()\n",
    "        i = 0\n",
    "        while i<len(words1) and i<len(words2):\n",
    "            if words1[i]==words2[i]:\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        j = 0\n",
    "        while len(words1)-j-1 >=0 and len(words2)-j-1 >=0:\n",
    "            if words1[len(words1)-j-1]==words2[len(words2)-j-1]:\n",
    "                j += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        if i+j >= min(len(words1), len(words2)):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        words1 = sentence1.split()\n",
    "        words2 = sentence2.split()\n",
    "        i, j = 0, 0\n",
    "        while i < len(words1) and i < len(words2) and words1[i] == words2[i]:\n",
    "            i += 1\n",
    "        while j < len(words1) - i and j < len(words2) - i and words1[-j - 1] == words2[-j - 1]:\n",
    "            j += 1\n",
    "        return i + j == min(len(words1), len(words2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        s1, s2 = sentence1.split(), sentence2.split()\n",
    "        n1, n2 = len(s1), len(s2)\n",
    "        if n1 < n2:\n",
    "            s1, s2, n1, n2 = s2, s1, n2, n1\n",
    "            sentence1, sentence2 = sentence2, sentence1\n",
    "        sentence1 = \" \" + sentence1 + \" \"\n",
    "        sentence2 = \" \" + sentence2 + \" \"\n",
    "        if sentence1.startswith(sentence2) or sentence1.endswith(sentence2):\n",
    "            return True\n",
    "        cnt = 0\n",
    "        flag = False\n",
    "        begin = 0\n",
    "\n",
    "        for i in range(n1):\n",
    "            if begin == n2:\n",
    "                return s1[-1] == s2[-1] and cnt < 2\n",
    "                # if not flag:\n",
    "                #     cnt += 1\n",
    "                # break\n",
    "            if s1[i] == s2[begin]:\n",
    "                begin += 1\n",
    "                flag = False\n",
    "            else:\n",
    "                if not flag:\n",
    "                    cnt += 1\n",
    "                flag = True\n",
    "        return cnt <= 1 and begin == n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        words1 = sentence1.split()\n",
    "        words2 = sentence2.split()\n",
    "\n",
    "        m, n = len(words1), len(words2)\n",
    "\n",
    "        if m > n:\n",
    "            words1, words2 = words2, words1\n",
    "            m, n = n, m\n",
    "\n",
    "        i, j = 0, 0\n",
    "        while i < m and j < n and words1[i] == words2[j]:\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "        while i < m and j < n and words1[m - 1] == words2[n - 1]:\n",
    "            m -= 1\n",
    "            n -= 1\n",
    "\n",
    "        return i == m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "\n",
    "\n",
    "        words1 = sentence1.split()\n",
    "        words2 = sentence2.split()\n",
    "\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < len(words1) and i < len(words2) and words1[i] == words2[i]:\n",
    "            i += 1\n",
    "        while j < len(words1) - i and j < len(words2) - i and words1[-j - 1] == words2[-j-1]:\n",
    "            j += 1\n",
    "\n",
    "        return i + j == min(len(words1), len(words2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        if(len(sentence1) < len(sentence2)):\n",
    "            sentence1, sentence2 = sentence2, sentence1\n",
    "        sentence1 = sentence1.split(' ')\n",
    "        sentence2 = sentence2.split(' ')\n",
    "        l1, r1 = 0, len(sentence1) - 1\n",
    "        l2, r2 = 0 ,len(sentence2) - 1\n",
    "        while(l1 <= r1 and l2 <= r2):\n",
    "            if(sentence1[l1] != sentence2[l2]):\n",
    "                break\n",
    "            l1 += 1\n",
    "            l2 += 1\n",
    "        while(l1 <= r1 and l2 <= r2):\n",
    "            if(sentence1[r1] != sentence2[r2]):\n",
    "                break\n",
    "            r1 -= 1\n",
    "            r2 -= 1\n",
    "        return l2 > r2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        if(len(sentence1) < len(sentence2)):\n",
    "            sentence1, sentence2 = sentence2, sentence1\n",
    "        sentence1 = sentence1.split(' ')\n",
    "        sentence2 = sentence2.split(' ')\n",
    "        l1, r1 = 0, len(sentence1) - 1\n",
    "        l2, r2 = 0 ,len(sentence2) - 1\n",
    "        while(l1 <= r1 and l2 <= r2):\n",
    "            if(sentence1[l1] != sentence2[l2]):\n",
    "                break\n",
    "            l1 += 1\n",
    "            l2 += 1\n",
    "        while(l1 <= r1 and l2 <= r2):\n",
    "            if(sentence1[r1] != sentence2[r2]):\n",
    "                break\n",
    "            r1 -= 1\n",
    "            r2 -= 1\n",
    "        return l2 > r2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:\n",
    "        q1, q2 = deque(sentence1.split()), deque(sentence2.split())\n",
    "        while q1 and q2 and q1[0] == q2[0]:\n",
    "            q1.popleft()\n",
    "            q2.popleft()\n",
    "        while q1 and q2 and q1[-1] == q2[-1]:\n",
    "            q1.pop()\n",
    "            q2.pop()\n",
    "        return not q1 or not q2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        dic = defaultdict(set)\n",
    "        for k,v in similarPairs:\n",
    "            dic[k].add(v)\n",
    "            dic[v].add(k)\n",
    "            \n",
    "        for i in range(len(sentence1)):\n",
    "            one,two = sentence1[i] , sentence2[i]\n",
    "            if one != two:\n",
    "                if two not in dic[one]:\n",
    "                    return False\n",
    "            #     continue\n",
    "            # if two in dic and one in dic[two]:\n",
    "            #     continue\n",
    "            # if one in dic and two in dic[one]:\n",
    "            #     continue\n",
    "            # return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "\n",
    "        m = collections.defaultdict(list)\n",
    "        for a, b in similarPairs:\n",
    "            m[a].append(b)\n",
    "            m[b].append(a)\n",
    "\n",
    "        for i in range(len(sentence1)):\n",
    "            s1 = sentence1[i]\n",
    "            s2 = sentence2[i]\n",
    "            if s1 != s2 and s2 not in m.get(s1, []):\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def areSentencesSimilar(self, words1, words2, pairs):\n",
    "        if len(words1) != len(words2): return False\n",
    "\n",
    "        pairset = set(map(tuple, pairs))\n",
    "        return all(w1 == w2 or (w1, w2) in pairset or (w2, w1) in pairset\n",
    "                   for w1, w2 in zip(words1, words2))\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1)!=len(sentence2): return False\n",
    "\n",
    "        d = {}\n",
    "        for p1,p2 in similarPairs:\n",
    "            if p1 not in d:\n",
    "                d[p1]=[p2]\n",
    "            else:\n",
    "                d[p1].append(p2)\n",
    "            if p2 not in d:\n",
    "                d[p2]=[p1]\n",
    "            else:\n",
    "                d[p2].append(p1)\n",
    "        \n",
    "        for p1,p2 in zip(sentence1,sentence2):\n",
    "            if p1==p2: continue\n",
    "            if p1 not in d or p2 not in d[p1]: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "\n",
    "        m=len(sentence1)\n",
    "        n=len(sentence2)\n",
    "        if m!=n:\n",
    "            return False\n",
    "        d=defaultdict(list)\n",
    "        for x,y in similarPairs:\n",
    "            d[x].append(y)\n",
    "\n",
    "        for i in range(m):\n",
    "            \n",
    "            if sentence1[i]==sentence2[i]:\n",
    "                continue\n",
    "            else:\n",
    "                if sentence1[i] in d:\n",
    "                    if sentence2[i] in d[sentence1[i]]:\n",
    "                        continue\n",
    "                if sentence2[i] in d:\n",
    "                    if sentence1[i] in d[sentence2[i]]:\n",
    "                        continue\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1)!= len(sentence2):\n",
    "            return False\n",
    "        \n",
    "        for i in range(len(sentence1)):\n",
    "            if sentence1[i] == sentence2[i]:\n",
    "                pass\n",
    "            elif [sentence1[i],sentence2[i]] in similarPairs:\n",
    "                pass\n",
    "            elif [sentence2[i],sentence1[i]] in similarPairs:\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        d = defaultdict(set)\n",
    "        for x, y in similarPairs:\n",
    "            d[x].add(y)\n",
    "            d[y].add(x)\n",
    "        \n",
    "        for i, w in enumerate(sentence1):\n",
    "            v = sentence2[i]\n",
    "            if not (v in d[w] or w in d[v] or v==w):\n",
    "                return False\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        size=len(sentence1)\n",
    "        if(size!=len(sentence2)):\n",
    "            return False\n",
    "        \n",
    "        memo=dict()\n",
    "\n",
    "        for v in similarPairs:\n",
    "            if(v[0] in memo):\n",
    "                memo[v[0]].append(v[1])\n",
    "            else:\n",
    "                memo[v[0]]=[v[1]]\n",
    "            if(v[1] in memo):\n",
    "                memo[v[1]].append(v[0])\n",
    "            else:\n",
    "                memo[v[1]]=[v[0]]\n",
    "            \n",
    "        \n",
    "        for i in range(size):\n",
    "            if(sentence1[i]==sentence2[i]):\n",
    "                continue\n",
    "            if(sentence1[i] not in memo or sentence2[i] not in memo[sentence1[i]]):\n",
    "                return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        pair_set = set(map(tuple, similarPairs))\n",
    "        for i, j in zip(sentence1, sentence2):\n",
    "            if i == j or (i, j) in pair_set or (j, i) in pair_set:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "\n",
    "        m = len(sentence1)\n",
    "        n = len(sentence2)\n",
    "\n",
    "        if m != n:\n",
    "            return False\n",
    "        \n",
    "        if sentence1 == sentence2:\n",
    "            return True\n",
    "        \n",
    "        pairs = set(map(tuple, similarPairs))\n",
    "\n",
    "        return all(w1 == w2 or (w1, w2) in pairs or (w2, w1) in pairs for w1, w2 in zip(sentence1, sentence2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1, sentence2, similarPairs):\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        sim = set(map(tuple, similarPairs))\n",
    "        for i in range(len(sentence1)):\n",
    "            s1, s2 = sentence1[i], sentence2[i]\n",
    "            if s1 == s2 or (s1, s2) in sim or (s2, s1) in sim:\n",
    "                continue\n",
    "            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1)!=len(sentence2):\n",
    "            return False\n",
    "        a=[list(n) for n in zip(sentence1,sentence2)]\n",
    "        b=[list(m) for m in zip(sentence2,sentence1)]\n",
    "        ans=[0 for o in range(len(sentence1))]\n",
    "        for i in range(len(sentence1)):\n",
    "            if a[i] in similarPairs or b[i] in similarPairs or sentence1[i]==sentence2[i]:\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def areSentencesSimilar(self, words1, words2, pairs):\n",
    "        if len(words1) != len(words2): return False\n",
    "\n",
    "        pairset = set(map(tuple, pairs))\n",
    "        return all(w1 == w2 or (w1, w2) in pairset or (w2, w1) in pairset\n",
    "                   for w1, w2 in zip(words1, words2))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        count = defaultdict(list)\n",
    "        for pair in similarPairs:\n",
    "            count[pair[0]].append(pair[1])\n",
    "            count[pair[1]].append(pair[0])\n",
    "\n",
    "        for idx, i in enumerate(sentence1):\n",
    "            if sentence2[idx] not in count[i] and i != sentence2[idx]:\n",
    "                return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:\n",
    "        if len(words1) != len(words2): return False\n",
    "\n",
    "        pairset = set(map(tuple, pairs))\n",
    "        return all(w1 == w2 or (w1, w2) in pairset or (w2, w1) in pairset\n",
    "                   for w1, w2 in zip(words1, words2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2): return False \n",
    "        sp = defaultdict(set)\n",
    "        for s in similarPairs:\n",
    "            sp[s[0]].add(s[1])\n",
    "            sp[s[1]].add(s[0])\n",
    "        \n",
    "        for i, w in enumerate(sentence1):\n",
    "            if (sentence2[i] not in sp[w]) and (sentence2[i] !=w):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1)!= len(sentence2):\n",
    "            return False\n",
    "        \n",
    "        for i in range(len(sentence1)):\n",
    "            if sentence1[i] == sentence2[i]:\n",
    "                pass\n",
    "            elif [sentence1[i],sentence2[i]] in similarPairs:\n",
    "                pass\n",
    "            elif [sentence2[i],sentence1[i]] in similarPairs:\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2) or 0 < len(similarPairs) < min(len(sentence1), len(sentence2)):\n",
    "            return False\n",
    "        if sentence1 == sentence2:\n",
    "            return True\n",
    "        \n",
    "        for i in range(len(sentence1)):\n",
    "            if sentence1[i] != sentence2[i] and [sentence1[i], sentence2[i]] not in similarPairs and [sentence2[i], sentence1[i]] not in similarPairs:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        similar_map = {}\n",
    "        for pair in similarPairs:\n",
    "            list1 = similar_map.get(pair[0], [])\n",
    "            list1.extend(pair)\n",
    "            similar_map[pair[0]] = list1\n",
    "            list2 = similar_map.get(pair[1], [])\n",
    "            list2.extend(pair)\n",
    "            similar_map[pair[1]] = list2\n",
    "        for word1, word2 in zip(sentence1, sentence2):\n",
    "            if word1 == word2 or word2 in similar_map.get(word1, []):\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        n = len(sentence1)\n",
    "        if n != len(sentence2):\n",
    "            return False\n",
    "        \n",
    "        d = {}\n",
    "        for x in similarPairs:\n",
    "            if x[0] in d:\n",
    "                d[x[0]].append(x[1])\n",
    "            else:\n",
    "                d[x[0]] = [x[1]]\n",
    "            if x[1] in d:\n",
    "                d[x[1]].append(x[0])\n",
    "            else:\n",
    "                d[x[1]] = [x[0]]\n",
    "        \n",
    "        for i in range(n):\n",
    "            if sentence1[i] != sentence2[i] and ((sentence1[i] not in d) or (sentence2[i] not in d[sentence1[i]])):\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        \n",
    "        #print(similarPairs)\n",
    "        for w1,w2 in zip(sentence1,sentence2):\n",
    "            #print(w1,w2)\n",
    "            #print([w2,w1] in similarPairs)\n",
    "            if w1!=w2 and [w1,w2] not in similarPairs and [w2,w1] not in similarPairs:\n",
    "                return False\n",
    "        return True\n",
    "            \n",
    "           \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def areSentencesSimilar(self, words1, words2, pairs):\n",
    "        if len(words1) != len(words2): return False\n",
    "\n",
    "        pairset = set(map(tuple, pairs))\n",
    "        return all(w1 == w2 or (w1, w2) in pairset or (w2, w1) in pairset\n",
    "                   for w1, w2 in zip(words1, words2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def areSentencesSimilar(self, words1, words2, pairs):\n",
    "        if len(words1) != len(words2): return False\n",
    "\n",
    "        pairset = set(map(tuple, pairs))\n",
    "        return all(w1 == w2 or (w1, w2) in pairset or (w2, w1) in pairset\n",
    "                   for w1, w2 in zip(words1, words2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2): return False\n",
    "        for i in range(len(sentence1)):\n",
    "            if [sentence1[i], sentence2[i]] in similarPairs or [sentence2[i], sentence1[i]] in similarPairs or sentence1[i] == sentence2[i]:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        if sentence1 == sentence2:\n",
    "            return True\n",
    "        for i, v in enumerate(sentence1):\n",
    "            if v == sentence2[i]:\n",
    "                continue\n",
    "            else:\n",
    "                is_similar = False\n",
    "                for v_list in similarPairs:\n",
    "                    if v in v_list and sentence2[i] in v_list:\n",
    "                        is_similar = True\n",
    "                        break\n",
    "                if not is_similar:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        for i in range(len(sentence1)):\n",
    "            if sentence1[i] == sentence2[i]:\n",
    "                pass\n",
    "            else:\n",
    "                j = 0\n",
    "                while j < len(similarPairs):\n",
    "                    if (similarPairs[j] == [sentence1[i],sentence2[i]]) or (similarPairs[j] == [sentence2[i],sentence1[i]]):\n",
    "                        break\n",
    "                    j += 1\n",
    "                if j == len(similarPairs):\n",
    "                    return False\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2): return False\n",
    "        # for i in range(len(sentence1)):\n",
    "        #     if [sentence1[i], sentence2[i]] in similarPairs or [sentence2[i], sentence1[i]] in similarPairs or sentence1[i] == sentence2[i]:\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         return False\n",
    "        # return True\n",
    "        pairset = set(map(tuple, similarPairs))\n",
    "        return all(w1==w2 or (w1,w2) in pairset or (w2,w1) in pairset for w1, w2 in zip(sentence1, sentence2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1)!=len(sentence2):\n",
    "            return False\n",
    "        sim = set(map(tuple, similarPairs))\n",
    "        for i in range(len(sentence1)):\n",
    "            s1, s2 = sentence1[i], sentence2[i]\n",
    "            if s1==s2 or (s1, s2) in sim or (s2, s1) in sim:\n",
    "                continue\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        n1 = len(sentence1)\n",
    "        n2 = len(sentence2)\n",
    "        if n1 != n2:\n",
    "            return False\n",
    "        similar_dict = collections.defaultdict(list)\n",
    "        for x, y in similarPairs:\n",
    "            similar_dict[x].append(y)\n",
    "            similar_dict[y].append(x)\n",
    "        for i in range(n1):\n",
    "            if sentence1[i] != sentence2[i] and sentence2[i] not in similar_dict[sentence1[i]]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        # 把相似性转化为hash表吧\n",
    "        hashmap = defaultdict(list)\n",
    "        for ch1, ch2 in similarPairs:\n",
    "            hashmap[ch1].append(ch2)\n",
    "            hashmap[ch2].append(ch1)\n",
    "\n",
    "        for i in range(len(sentence1)):\n",
    "            s1 = sentence1[i]\n",
    "            s2 = sentence2[i]\n",
    "            if s1 == s2 or s1 in hashmap[s2] or s2 in hashmap[s1]:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        similar = set(map(tuple, similarPairs))\n",
    "        for i in range(len(sentence1)):\n",
    "            s1, s2 = sentence1[i], sentence2[i]\n",
    "            if s1 == s2 or (s1, s2) in similar or (s2, s1) in similar:\n",
    "                continue\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Input: sentence1 = [\"great\",\"acting\",\"skills\"], sentence2 = [\"fine\",\"drama\",\"talent\"], similarPairs = [[\"great\",\"fine\"],[\"drama\",\"acting\"],[\"skills\",\"talent\"]]\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        sim = set(map(tuple,similarPairs))\n",
    "        for i in range(len(sentence1)):\n",
    "            s1, s2 = sentence1[i], sentence2[i]\n",
    "            if s1 == s2 or (s1, s2) in sim or (s2, s1) in sim:\n",
    "                continue \n",
    "            return False \n",
    "        return True \n",
    "    \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        for w1,w2 in zip(sentence1,sentence2):\n",
    "            if w1 == w2:\n",
    "                continue\n",
    "            elif [w1, w2] not in similarPairs and [w2, w1] not in similarPairs:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2): return False\n",
    "\n",
    "        pairset = set(map(tuple, similarPairs))\n",
    "        return all(w1 == w2 or (w1, w2) in pairset or (w2, w1) in pairset\n",
    "                   for w1, w2 in zip(sentence1, sentence2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def areSentencesSimilar(self, words1, words2, pairs):\n",
    "        if len(words1) != len(words2): return False\n",
    "\n",
    "        pairset = set(map(tuple, pairs))\n",
    "        return all(w1 == w2 or (w1, w2) in pairset or (w2, w1) in pairset\n",
    "                   for w1, w2 in zip(words1, words2))\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        label = 0\n",
    "        for i in range(len(sentence1)):\n",
    "            if sentence1[i] != sentence2[i]:\n",
    "                label = 0\n",
    "                for j in range(len(similarPairs)):\n",
    "                    if (similarPairs[j][0] == sentence1[i] and similarPairs[j][1] == sentence2[i]) or (similarPairs[j][0] == sentence2[i] and similarPairs[j][1] == sentence1[i]):\n",
    "                        label = 1\n",
    "                        break\n",
    "                if label == 0:\n",
    "                    return False\n",
    "        return True\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        \n",
    "        similarity = collections.defaultdict(set)\n",
    "        for p in similarPairs:\n",
    "            s, t = p\n",
    "            if s <= t:\n",
    "                similarity[s].add(t)\n",
    "            else:\n",
    "                similarity[t].add(s)\n",
    "        \n",
    "        i = 0\n",
    "        while i < len(sentence1):\n",
    "            w1, w2 = sentence1[i], sentence2[i]\n",
    "            w1, w2 = (w1, w2) if w1 <= w2 else (w2, w1)\n",
    "\n",
    "            if w1 == w2:\n",
    "                i += 1\n",
    "            else:\n",
    "                if w1 in similarity and w2 in similarity[w1]:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "\n",
    "        similar_pair_mapper = collections.defaultdict(set)\n",
    "\n",
    "        for pair1, pair2 in similarPairs:\n",
    "            similar_pair_mapper[pair1].add(pair2)\n",
    "            similar_pair_mapper[pair2].add(pair1)\n",
    "\n",
    "        for index, row1 in enumerate(sentence1):\n",
    "            row2 = sentence2[index]\n",
    "\n",
    "            if row1 == row2:\n",
    "                continue\n",
    "\n",
    "            row1_similar_pairs = similar_pair_mapper[row1]\n",
    "            row2_similar_pairs = similar_pair_mapper[row2]\n",
    "\n",
    "            if not (row2 in row1_similar_pairs and row1 in row2_similar_pairs):\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        l1,l2=len(sentence1),len(sentence2)\n",
    "        if l1!=l2: return False\n",
    "        dt1,dt2=dict(),dict()\n",
    "        sen=set(sentence1+sentence2)\n",
    "        for i in sen:\n",
    "            dt1[i]=set([i])\n",
    "\n",
    "        for t in similarPairs:\n",
    "            if t[0] in dt1:\n",
    "                dt1[t[0]].add(t[1])\n",
    "            if t[1] in dt1:\n",
    "                dt1[t[1]].add(t[0])\n",
    "            \n",
    "            # if t[1] in dt2:\n",
    "            #     dt2[t[1]].add(t[0])\n",
    "            # else:\n",
    "            #     dt2[t[1]]=set([t[0],t[1]])\n",
    "        \n",
    "        for i in range(l1):\n",
    "            t1=sentence1[i]\n",
    "            t2=sentence2[i]\n",
    "            if t2 in dt1[t1]:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        pairs = dict()\n",
    "        for p in similarPairs:\n",
    "            if p[0] not in pairs:\n",
    "                pairs[p[0]] = set()\n",
    "            pairs[p[0]].add(p[1])\n",
    "            if p[1] not in pairs:\n",
    "                pairs[p[1]] = set()\n",
    "            pairs[p[1]].add(p[0])\n",
    "        \n",
    "        for i in range(len(sentence1)):\n",
    "            if sentence1[i] == sentence2[i]:\n",
    "                continue\n",
    "            if sentence1[i] not in pairs or sentence2[i] not in pairs:\n",
    "                return False\n",
    "            if sentence2[i] not in pairs[sentence1[i]]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        sent1 = ' '.join(sentence1)\n",
    "        sent2 = ' '.join(sentence2)\n",
    "        sim = set(map(tuple, similarPairs))\n",
    "        if sent1 == sent2:\n",
    "            return True\n",
    "        list1 = []\n",
    "        for i in range(len(sentence1)):\n",
    "            list1.append([sentence1[i],sentence2[i]])\n",
    "        for j in range(len(list1)):\n",
    "            s1,s2 = list1[j][0],list1[j][1]\n",
    "            if s1==s2 or (s1,s2) in sim or (s2,s1) in sim:\n",
    "                print(j)\n",
    "                continue\n",
    "       \n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        l = len(sentence1)\n",
    "        d={}\n",
    "        for pair in similarPairs:\n",
    "            if pair[0] in d:\n",
    "                d[pair[0]].append(pair[1])\n",
    "            else:\n",
    "                d[pair[0]] = [pair[1]]\n",
    "            if pair[1] in d:\n",
    "                d[pair[1]].append(pair[0])\n",
    "            else:\n",
    "                d[pair[1]] = [pair[0]]\n",
    "        for i in range(l):\n",
    "            if sentence1[i] == sentence2[i]:\n",
    "                continue\n",
    "            if not (sentence1[i] in d and sentence2[i] in d and sentence1[i] in d[sentence2[i]]):\n",
    "                return False\n",
    "        return True\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        n, m = len(sentence1), len(sentence2)\n",
    "        if n != m:\n",
    "            return False\n",
    "        sim_dic = defaultdict(list)\n",
    "        for a, b in similarPairs:\n",
    "            sim_dic[a].append(b)\n",
    "            sim_dic[b].append(a)\n",
    "        for s1, s2 in zip(sentence1, sentence2):\n",
    "            if not(s1 == s2 or s2 in sim_dic[s1] or s1 in sim_dic[s2]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        n, m = len(sentence1), len(sentence2)\n",
    "        if n != m:\n",
    "            return False\n",
    "        store = collections.defaultdict(set)\n",
    "        for a, b in similarPairs:\n",
    "            store[a].add(b)\n",
    "            store[a].add(a)\n",
    "            store[b].add(b)\n",
    "            store[b].add(a)\n",
    "        for i in range(n):\n",
    "            if sentence1[i] == sentence2[i]:\n",
    "                continue\n",
    "            if sentence1[i] not in store or sentence2[i] not in store:\n",
    "                return False\n",
    "            if sentence1[i] not in store[sentence2[i]] or sentence2[i] not in store[sentence1[i]]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        m, n = len(sentence1), len(sentence2)\n",
    "        if m != n: return False\n",
    "        cnt = set(map(tuple, similarPairs))\n",
    "        for x, y in zip(sentence1, sentence2):\n",
    "            if x == y: continue\n",
    "            if (x, y) not in cnt and (y, x) not in cnt:\n",
    "                return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def areSentencesSimilar(self, words1, words2, pairs):\n",
    "        if len(words1) != len(words2): return False\n",
    "\n",
    "        pairset = set(map(tuple, pairs))\n",
    "        return all(w1 == w2 or (w1, w2) in pairset or (w2, w1) in pairset\n",
    "                   for w1, w2 in zip(words1, words2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        m, n = len(sentence1), len(sentence2)\n",
    "        if m != n: return False\n",
    "        for x, y in zip(sentence1, sentence2):\n",
    "            if x == y: continue\n",
    "            if [x, y] not in similarPairs and [y, x] not in similarPairs:\n",
    "                return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "\n",
    "        m=len(sentence1)\n",
    "        n=len(sentence2)\n",
    "        if m!=n:\n",
    "            return False\n",
    "        d=defaultdict(list)\n",
    "        for x,y in similarPairs:\n",
    "            d[x].append(y)\n",
    "\n",
    "        for i in range(m):\n",
    "            \n",
    "            if sentence1[i]==sentence2[i]:\n",
    "                continue\n",
    "            else:\n",
    "                if sentence1[i] in d:\n",
    "                    if sentence2[i] in d[sentence1[i]]:\n",
    "                        continue\n",
    "                if sentence2[i] in d:\n",
    "                    if sentence1[i] in d[sentence2[i]]:\n",
    "                        continue\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        simPairDict = {}\n",
    "        if similarPairs:\n",
    "            for pair in similarPairs:\n",
    "                if pair[0] in simPairDict:\n",
    "                    simPairDict[pair[0]].append(pair[1])  \n",
    "                else: \n",
    "                    simPairDict[pair[0]] = [pair[1]]\n",
    "                if pair[1] in simPairDict:\n",
    "                    simPairDict[pair[1]].append(pair[0])  \n",
    "                else: \n",
    "                    simPairDict[pair[1]] = [pair[0]]\n",
    "        if len(sentence1) != len(sentence2):\n",
    "            return False\n",
    "        for i in range(len(sentence1)):\n",
    "            if sentence1[i] not in simPairDict or sentence2[i] not in simPairDict[sentence1[i]]:\n",
    "                if sentence1[i]!= sentence2[i]:\n",
    "                    return False\n",
    "            # elif sentence2[i] not in simPairDict[sentence1[i]] :\n",
    "            #     return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:\n",
    "        if len(sentence1) != len(sentence2): return False\n",
    "\n",
    "        pairset = set(map(tuple, similarPairs))\n",
    "        return all(w1 == w2 or (w1, w2) in pairset or (w2, w1) in pairset for w1, w2 in zip(sentence1, sentence2))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
